Maps include geographic drawings showing countries, cities, rivers, bodies of water, mountains, and other features of interest. Labeling cartographic features is a fundamental part of map-making. Placing each label optimally with respect to its corresponding feature invariably produces labels overlapping each other or too close to each other. As this results in confusion and unacceptable maps, methods to reposition labels or not draw them at all must be used to create a map that conveys as much information as possible.
Tagging graphical objects with text labels is a fundamental task in the design of many types of informational graphics. This problem is seen in its most essential form in cartography, but it also arises frequently in the production of other informational graphics such as scatter plots. The quality of a labeling is determined essentially by the degree to which labels obscure other labels or features of the underlying graphic. The goal is to choose positions for the labels that do not give rise to label overlaps and that minimize obscuration of features. Construction of a good labeling is thus a combinatorial optimization problem, which has been shown to be NP-hard (Marks and Shieber, 1991). As a hypothetical baseline algorithm, randomly choosing positions for each label generates a poor labeling, both aesthetically, and as quantified using a metric that counts the number of conflicted labels, i.e., those that obscure point features or other labels.
In addition to geographical and technical maps, there are many labeling applications relating to graph layouts and drawings. These applications include, but are not limited to, areas such as database design (e.g. entity relationship diagrams), software engineering including CASE, software debugging, complex web pages, CAD drafting, complex electrical diagrams, and telecommunications and communications networking In fact, the labeling of the graphical features of any drawing is generally necessary because it conveys information essential to understanding the drawing. For complex and information rich drawings, computer aided labeling is increasingly employed.
As used in the present specification, the term “map” is used to include both geographical and technical maps as well as graph layouts and drawings. The term “label” is used to refer to text or other indicia to be placed on a map.
A system and method for labeling objects on maps while avoiding collisions with other labels has been sought after. Some apparently powerful algorithms for automatic label placement on maps use heuristics that capture considerable cartographic expertise but are hampered by provably inefficient methods of search and optimization.
This patent discloses a system and method for label placement that achieves the twin goals of practical efficiency and high labeling quality by employing cartographic heuristics.